package com.example.targetOffer.controller;

import java.util.HashMap;

/**
 * 动态规划之 解决重叠子问题
 */
public class DP_01 {

    //用递归的方式求解斐波那契数列的第6项的值, 即求 F6
    public static void main(String[] args) {
        fib(6);
        fib2(6);
    }

    //使用递归来实现
    public static int fib(int n) {
        if (n < 2) return 1;
        int fn = fib(n - 1) + fib(n - 2);
        System.out.println("F" + n + " = " + "F" + (n - 1) + " + F" + (n - 2) + " = " + fn);
        return fn;
    }

    //使用动态规划来处理
    public static int fib2(int n) {
        System.out.println("--------------------------");
        //利用HashMap保存已处理的子问题
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        map.put(1, 1);

        int fi = 0;
        for (int i = 2; i <= n; i++) {
            fi = map.get(i - 1) + map.get(i - 2);

            //已处理的子问题放入map中
            map.put(i, fi);
            System.out.println("F" + i + " = " + "F" + (i - 1) + " + F" + (i - 2) + " = " + fi);
        }
        map.clear();
        return fi;
    }
}
